
//2563.统计公平数对的数目
class Solution {
public:
    long long countFairPairs(vector<int>& nums, int lower, int upper) {
        //lower-nums[j]<=nums[i]<=upper-nums[j]
        //当nums[i]在增大的时候，lower-nums[j]和upper-nums[j]都是在减小的
        sort(nums.begin(),nums.end());
        int n=nums.size();
        int left=n-1,right=n-1;
        long long ret=0;
        for(int i=0;i<n;i++)
        {
            while(left>=0&&nums[left]>=lower-nums[i]) left--; //直到nums[left]<lower-nums[i]即nums[i]<lower-nums[left]
            while(right>=0&&nums[right]>upper-nums[i]) right--;  //直到nums[right]<=upper-nums[i]

            //此时的[left+1,right+1)是满足条件的
            ret+=min(right+1,i)-min(left+1,i);
        }
        return ret/2;
    }
};